package leetcode.code0657;

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	public int cutOffTree(List<List<Integer>> forest) {
		int m = forest.size();
		int n = forest.get(0).size();
		int[][] trees = new int[m][n];
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		for (int i = 0; i < m; i++) {
			List<Integer> row = forest.get(i);
			for (int j = 0; j < n; j++) {
				int num = row.get(j);
				trees[i][j] = num;
				if (num > 1) {
					queue.add(new int[] { num, i, j });
				}
			}
		}
		int ans = 0;
		int x = 0, y = 0;
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int u = cur[1], v = cur[2];
			int dist = this.dist(x, y, u, v, trees);
			if (dist == -1) {
				return -1;
			}
			ans += dist;
			x = u;
			y = v;
		}
		return ans;
	}

	private int dist(int x, int y, int u, int v, int[][] trees) {
		if (x == u && y == v) {
			return 0;
		}
		int m = trees.length, n = trees[0].length;
		boolean[] been = new boolean[m * n];
		been[this.index(x, y, n)] = true;
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y, 0 });
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			x = cur[0];
			y = cur[1];
			int dist = cur[2] + 1;
			for (int i = 0; i < 8; i += 2) {
				int nextx = x + d[i], nexty = y + d[i + 1];
				if (nextx == u && nexty == v) {
					return dist;
				}
				int nextIndex = this.index(nextx, nexty, n);
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && !been[nextIndex]
						&& trees[nextx][nexty] != 0) {
					queue.add(new int[] { nextx, nexty, dist });
					been[nextIndex] = true;
				}
			}
		}
		return -1;
	}

	public int index(int i, int j, int n) {
		return i * n + j;
	}

	@Override
	public void debug4() {
		H.compare(6, this.cutOffTree(H.str2intlist1("[[2,3,4],[0,0,5],[8,7,6]]")));
		H.compare(6, this.cutOffTree(H.str2intlist1("[[1,2,3],[0,0,4],[7,6,5]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
